P2014 选课

洛谷P2014选课

一道树形DP题。

f[i][j] 表示i个点选j门课程的最大学分。

递推方程：

for(int a=n;a>0;a--)//总共选择多少
    for(int b=0;b<a;b++)//分别选择多少(b,a-b)
        f[x][a]=max(f[x][a],f[x][a-b]+f[u][b]);
//都不遍历0的原因是f[i][0]无论怎样都是0

我们可以证明在 \(j\leq m\)时值都是正确的，剩下的不用管啦么的时间！

#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=305;
inline int read()
{
    int x,w=1;char c=getchar();
    while(!isdigit(c))c=getchar();
    if(c=='-')w=-1,c=getchar();
    x=c-'0';c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*w;
}
int n,m;
int f[maxn][maxn];
vector <int>son[maxn];
void dfs(int x)
{
    f[x][0]=0;
    for(int i=0;i<son[x].size();i++)
    {
        int u=son[x][i];
        dfs(u);
        for(int a=n;a>0;a--)
            for(int b=0;b<a;b++)
            f[x][a]=max(f[x][a],f[x][a-b]+f[u][b]);
    }
}
int main()
{
    n=read(),m=read()+1;
    for(int i=1;i<=n;i++){
        son[read()].push_back(i); f[i][1]=read();
    }
    f[0][0]=f[0][1]=0;
    n++;
    dfs(0);
    printf("%d\n",f[0][m]);
    return 0;
}